package com.javaDemo.ti;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @ClassName: LRUCacheDemo
 * @Auther: csy
 * @Date: 2023/7/15 10:00
 * @Description: LRU（Least Recently Used）缓存算法演示
 *               LRU是一种常用的缓存淘汰策略，当缓存满时，优先淘汰最近最少使用的数据
 */
public class LRUCacheDemo {

    public static void main(String[] args) {
        System.out.println("===== 使用LinkedHashMap实现的LRU缓存 =====");
        LRUCacheWithLinkedHashMap<Integer, String> cache1 = new LRUCacheWithLinkedHashMap<>(3);
        cache1.put(1, "一");
        cache1.put(2, "二");
        cache1.put(3, "三");
        System.out.println("初始缓存: " + cache1);
        
        // 访问键1，使其成为最近使用的元素
        System.out.println("获取键1: " + cache1.get(1));
        System.out.println("访问后缓存: " + cache1);
        
        // 添加新元素，导致最久未使用的元素被移除
        cache1.put(4, "四");
        System.out.println("添加键4后缓存: " + cache1);
        
        System.out.println("\n===== 自定义实现的LRU缓存 =====");
        LRUCache<Integer, String> cache2 = new LRUCache<>(3);
        cache2.put(1, "一");
        cache2.put(2, "二");
        cache2.put(3, "三");
        System.out.println("初始缓存: " + cache2);
        
        // 访问键1，使其成为最近使用的元素
        System.out.println("获取键1: " + cache2.get(1));
        System.out.println("访问后缓存: " + cache2);
        
        // 添加新元素，导致最久未使用的元素被移除
        cache2.put(4, "四");
        System.out.println("添加键4后缓存: " + cache2);
    }
    
    /**
     * 方法一：使用LinkedHashMap实现LRU缓存
     * LinkedHashMap本身就支持按访问顺序排序，非常适合实现LRU缓存
     */
    static class LRUCacheWithLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
        private final int capacity; // 缓存容量
        
        /**
         * 构造函数
         * 
         * @param capacity 缓存容量
         */
        public LRUCacheWithLinkedHashMap(int capacity) {
            // 初始容量、负载因子、访问顺序（true表示按访问顺序排序，最近访问的元素会被移到链表末尾）
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }
        
        /**
         * 当Map中的元素数量超过容量时，自动移除最久未使用的元素
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;
        }
    }
    
    /**
     * 方法二：自定义实现LRU缓存
     * 使用HashMap + 双向链表实现
     */
    static class LRUCache<K, V> {
        private final int capacity; // 缓存容量
        private final Map<K, Node<K, V>> cache; // 存储键到节点的映射
        private final Node<K, V> head; // 双向链表头节点（最久未使用）
        private final Node<K, V> tail; // 双向链表尾节点（最近使用）
        
        /**
         * 构造函数
         * 
         * @param capacity 缓存容量
         */
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap<>(capacity);
            // 创建哨兵节点，简化边界情况处理
            this.head = new Node<>(null, null);
            this.tail = new Node<>(null, null);
            // 初始化链表
            head.next = tail;
            tail.prev = head;
        }
        
        /**
         * 获取缓存中的值
         * 
         * @param key 键
         * @return 值，如果不存在则返回null
         */
        public V get(K key) {
            Node<K, V> node = cache.get(key);
            if (node == null) {
                return null;
            }
            // 将访问的节点移动到链表尾部（表示最近使用）
            moveToTail(node);
            return node.value;
        }
        
        /**
         * 添加或更新缓存
         * 
         * @param key 键
         * @param value 值
         */
        public void put(K key, V value) {
            Node<K, V> node = cache.get(key);
            
            if (node != null) {
                // 键已存在，更新值并移到链表尾部
                node.value = value;
                moveToTail(node);
            } else {
                // 键不存在，创建新节点
                Node<K, V> newNode = new Node<>(key, value);
                cache.put(key, newNode);
                addToTail(newNode);
                
                // 如果超出容量，移除链表头部的节点（最久未使用）
                if (cache.size() > capacity) {
                    Node<K, V> removed = removeHead();
                    cache.remove(removed.key);
                }
            }
        }
        
        /**
         * 将节点移动到链表尾部（表示最近使用）
         */
        private void moveToTail(Node<K, V> node) {
            // 从当前位置移除
            removeNode(node);
            // 添加到尾部
            addToTail(node);
        }
        
        /**
         * 从链表中移除指定节点
         */
        private void removeNode(Node<K, V> node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        
        /**
         * 将节点添加到链表尾部
         */
        private void addToTail(Node<K, V> node) {
            node.prev = tail.prev;
            node.next = tail;
            tail.prev.next = node;
            tail.prev = node;
        }
        
        /**
         * 移除链表头部的节点（最久未使用的节点）
         * 
         * @return 被移除的节点
         */
        private Node<K, V> removeHead() {
            Node<K, V> removed = head.next;
            removeNode(removed);
            return removed;
        }
        
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{");
            Node<K, V> current = head.next;
            while (current != tail) {
                sb.append(current.key).append("=").append(current.value);
                current = current.next;
                if (current != tail) {
                    sb.append(", ");
                }
            }
            sb.append("}");
            return sb.toString();
        }
        
        /**
         * 双向链表节点
         */
        private static class Node<K, V> {
            K key;
            V value;
            Node<K, V> prev;
            Node<K, V> next;
            
            Node(K key, V value) {
                this.key = key;
                this.value = value;
            }
        }
    }
}